package _go

func levelOrder(root *TreeNode) [][]int {

	if root == nil {
		return [][]int{}
	}

	var q_ary, h_ary []*TreeNode
	var res [][]int

	//前一层 先把根节点放入前一层切片 后一层默认为空
	q_ary = append(q_ary, root)
	//下一层

	//遍历前一层数组 将叶子节点放入后一层数组 循环完成后 后一层赋值给前一层 继续便利并打印
	fg := true
	for fg {
		//临时数组 存放一层的结果
		resTmp := []int{}
		for i := 0; i < len(q_ary); i++ {
			resTmp = append(resTmp, q_ary[i].Val)

			//有叶子节点 放入后边的队列
			if q_ary[i].Left != nil {
				h_ary = append(h_ary, q_ary[i].Left)
			}

			//有叶子节点 放入后边的队列
			if q_ary[i].Right != nil {
				h_ary = append(h_ary, q_ary[i].Right)
			}
		}
		//结果输出
		res = append(res, resTmp)
		//下一层 继续便利
		q_ary = h_ary

		//结束判断条件
		if len(h_ary) == 0 {
			fg = false
		}
		//清空下一层的切片
		h_ary = []*TreeNode{}
	}
	return res
}
